/**
 * 879.盈利计划
 */
public class Exerciser10 {
    /**
     * 滚动数组的优化
     * @param n
     * @param minProfit
     * @param group
     * @param profit
     * @return
     */
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)1e9 + 7;

        int[][] dp = new int[n + 1][minProfit + 1];
        // 初始化：
        for(int j = 0;j <= n;j++) {
            dp[j][0] = 1;
        }
        for(int i = 1;i <= len;i++) {
            for(int j = n;j >= group[i - 1];j--) {
                for(int k = minProfit;k >= 0;k--) {
                    dp[j][k] += dp[j - group[i - 1]][Math.max(0,k - profit[i - 1])];
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[n][minProfit];
    }

    public int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)1e9 + 7;

        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        // 初始化：
        for(int j = 0;j <= n;j++) {
            dp[0][j][0] = 1;
        }
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= n;j++) {
                for(int k = 0;k <= minProfit;k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= group[i - 1]) {
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][Math.max(0,k - profit[i - 1])];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }
}
